#include <iostream>
#include <stack>

using namespace std;

enum Direction{None = 0, Up, Left, Down = 4, Right = 8, All = 15};


//Direction& operator |=(Direction &posA, const Direction &posB){
//	/*Direction d = (Direction)(posA | posB);
//	return d;*/
//	posA = (Direction)(posA | posB);
//	return posA;
//}

class Position{
public:
	int _x;
	int _y;
	int _direction;	

	// Position(int x = 0, int y = 0, Direction direction = Direction::None) : _x(x), _y(y), _direction(direction){}
	Position(int x = 0, int y = 0) : _x(x), _y(y), _direction(Direction::None){}

	// Position(const Position &pos) : _x(pos._x), _y(pos._y), _direction(1){}

	bool operator ==(const Position &pos){
		return pos._x == this->_x && pos._y == this->_y;	
	}

	Position operator= (const Position &pos){
		this->_x = pos._x;
		this->_y = pos._y;
		this->_direction = Direction::None;
		// this->_direction = pos._direction;

		return *this;
	}

	Position move(Direction direction){
		Position nextPos = *this;
		switch(direction){
		case Up:
			--nextPos._y;
			// nextPos._direction = nextPos._direction | Direction::Down;
			nextPos._direction = Direction::Down;
			break;
		case Left:
			--nextPos._x;
			// nextPos._direction |= Direction::Right;
			nextPos._direction = Direction::Right;
			break;
		case Down:
			++nextPos._y;
			nextPos._direction = Direction::Up;
			break;
		case Right:
			++nextPos._x;
			nextPos._direction = Direction::Left;
			break;
		default:
			break;
		}
		return nextPos;
	}
};

bool find(int arr[][10], Position endPos, stack<Position> &pathStack){
	Position curPos = pathStack.top();
	/* // below will not call copy constructor
	Position curPos;
	curPos = pathStack.top();
	*/ 
	if(curPos == endPos)
		return true;
	if(0 == arr[curPos._y][curPos._x]){
		pathStack.pop();
		return false;
	}
	bool result = false;
	while(!pathStack.empty()){
		curPos = pathStack.top();
		if(0 == (curPos._direction & Direction::Left)){
			curPos._direction |= Direction::Left;
			/*pathStack.pop();
			pathStack.push(curPos);*/
			pathStack.top()._direction |= Direction::Left;

			pathStack.push(curPos.move(Direction::Left));
			result = find(arr, endPos, pathStack);
		}
		else if(0 == (curPos._direction & Direction::Down)){
			curPos._direction |= Direction::Down;
			/*pathStack.pop();
			pathStack.push(curPos);*/
			pathStack.top()._direction |= Direction::Down;
			pathStack.push(curPos.move(Direction::Down));
			result = find(arr, endPos, pathStack);
		}
		else if(0 == (curPos._direction & Direction::Right)){
			curPos._direction |= Direction::Right;
			/*pathStack.pop();
			pathStack.push(curPos);*/
			pathStack.top()._direction |= Direction::Right;
			pathStack.push(curPos.move(Direction::Right));
			result = find(arr, endPos, pathStack);
		}
		else if(0 == (curPos._direction & Direction::Up)){
			curPos._direction |= Direction::Up;
			/*pathStack.pop();
			pathStack.push(curPos);*/
			pathStack.top()._direction |= Direction::Up;
			pathStack.push(curPos.move(Direction::Up));
			result = find(arr, endPos, pathStack);
		}
		else{
			pathStack.pop();
			curPos = pathStack.top();
		}
		if(result)
			return result;
	}
	return result;
};

int mazemain(){
	int arr[][10] = {
	//	 0  1  2  3  4  5  6  7  8  9	 //
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  // 0 
		{0, 1, 1, 0, 1, 1, 1, 0, 1, 0},  // 1
		{0, 1, 1, 0, 1, 1, 1, 0, 1, 0},  // 2
		{0, 1, 1, 1, 1, 0, 0, 1, 1, 0},  // 3
		{0, 1, 0, 0, 0, 1, 1, 1, 1, 0},  // 4
		{0, 1, 1, 1, 0, 1, 1, 1, 1, 0},  // 5
		{0, 1, 0, 1, 1, 1, 0, 1, 1, 0},  // 6
		{0, 1, 0, 0, 0, 0, 0, 0, 1, 0},  // 7
		{0, 0, 1, 1, 1, 1, 1, 1, 1, 0},  // 8
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}   // 9
	};

	int arr2[][4] = {
		//	 0  1  2  3
			{0, 0, 0, 0},  // 0 
			{0, 1, 1, 0},  // 1
			{0, 0, 1, 0},  // 2
			{0, 0, 0, 0},  // 3
	};

	Position pa(1, 1);
	Position p2 = pa.move(Direction::Right);
	Position p3 = p2.move(Direction::Left);
	p3 = p2.move(Direction::Down);

	Position start(1, 1), end(2, 8);
	start._direction |= Direction::Left;
	start._direction |= Direction::Up;

	stack<Position> pathStack;
	pathStack.push(start);

	Position end2(2, 2);
	// bool b2 = find(arr2, end2, pathStack);

	bool b = find(arr, end, pathStack);

	return 0;
}